/*
 * @lc app=leetcode.cn id=1005 lang=cpp
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
class Solution
{
    static bool cmp(int &a, int &b)
    {
        //从大到小排序
        return abs(a) > abs(b);
    }

public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        // k次取反的最大值 很简单吧 先排序 从小到大依次取反
        //我傻逼了 没看题 他可以对同一个元素反转多次
        //首先对于负数 需要将绝对值大的负数反转 如果多了 就将小的非负数反转
        sort(nums.begin(), nums.end(), cmp);
        int res = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (k > 0 && nums[i] < 0)
            {
                nums[i] = nums[i] * -1;
                k--;
            }
            res += nums[i];
        }
        // k仍然大于0
        if (k > 0 && k % 2 != 0)
        {
            res -= nums[nums.size() - 1] * 2;
        }
        return res;
    }
};
// @lc code=end
